#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 1000

void insertion_sort(int *p, int n);

int main(void)
{
	int i;
	int a[N];

	srand((int)time(NULL));

	for (i = 0; i < N; ++i)
	{
		a[i] = rand() % 10000;
	}

	insertion_sort(a, N);

	for (i = 0; i < N; ++i)
		printf("%d ", a[i]);
	printf("\n");

	return 0;
}

void insertion_sort(int *p, int n)
{
	int i, j;
	int tmp;
	for (i = 1; i <= n; ++i)
	{
		tmp = p[i];
		for (j = i; j > 0 && p[j-1] > tmp; --j)
			p[j] = p[j-1];
		p[j] = tmp;
	}
}